#ifndef POLY
#define POLY

#include <stdlib.h>
#include <malloc.h>
#include <math.h>

// 多项式链表的节点
typedef struct _Node
{
	double c;
	double e;
	struct _Node *next;
} Node;

// 多项式链表
typedef struct
{
	Node *head;
} Poly;

// 创建新节点
Node *NewNode(double c, double e)
{
	Node *node = (Node *)malloc(sizeof(Node));
	node->c = c;
	node->e = e;
	node->next = NULL;
	return node;
}

// 创建新链表
Poly *NewPoly()
{
	Poly *poly = (Poly *)malloc(sizeof(Poly));
	poly->head = NewNode(0, 0);
	poly->head->next = NULL;
	return poly;
}

// 将节点加到多项式上
Poly *AddNode(Poly *poly, Node *node)
{
	Node *temp;
	Node *p;
	int flag = 0;

	if (node->c != 0)
	{
		for (p = poly->head; p->next; p = p->next)
		{
			if (node->e > p->next->e)
			{
				flag = 1;
				temp = p->next;
				p->next = node;
				node->next = temp;
				break;
			}
			else if (node->e == p->next->e)
			{
				flag = 1;
				p->next->c += node->c;
				if (p->next->c == 0)
				{
					temp = p->next;
					p->next = temp->next;
					free(temp);
				}
				free(node);
				break;
			}
		}
		if (!flag)
		{
			p->next = node;
			node->next = NULL;
		}
	}
	else
	{
		free(node);
	}
	return poly;
}

// 克隆多项式
Poly *ClonePoly(Poly *poly)
{
	Poly *clone = NewPoly();
	for (Node *p = poly->head; p->next; p = p->next)
	{
		AddNode(clone, NewNode(p->next->c, p->next->e));
	}
	return clone;
}

// 清空多项式
void ClearPoly(Poly *poly)
{
	Node *temp;
	while (poly->head)
	{
		temp = poly->head;
		poly->head = temp->next;
		free(temp);
	}
}

// 多项式相加
Poly *AddPoly(Poly *poly1, Poly *poly2)
{
	for (Node *p = poly2->head; p->next; p = p->next)
	{
		AddNode(poly1, NewNode(p->next->c, p->next->e));
	}
	return poly1;
}

// 多项式加上数字
Poly *AddNum(Poly *poly, double num)
{
	AddNode(poly, NewNode(num, 0));
	return poly;
}

// 多项式取负
Poly *NegPoly(Poly *poly)
{
	for (Node *node = poly->head; node->next; node = node->next)
	{
		node->next->c = -node->next->c;
	}
	return poly;
}

// 多项式相减
Poly *SubPoly(Poly *poly1, Poly *poly2)
{
	for (Node *p = poly2->head; p->next; p = p->next)
	{
		AddNode(poly1, NewNode(-p->next->c, p->next->e));
	}
	return poly1;
}

// 多项式相乘
Poly *MulPoly(Poly *poly1, Poly *poly2)
{
	Poly *poly = NewPoly();
	for (Node *p = poly1->head; p->next; p = p->next)
	{
		for (Node *q = poly2->head; q->next; q = q->next)
		{
			AddNode(poly, NewNode(p->next->c * q->next->c, p->next->e + q->next->e));
		}
	}
	ClearPoly(poly1);
	poly1->head = poly->head;
	return poly1;
}

// 多项式乘上数字
Poly *MulNum(Poly *poly, double num)
{
	for (Node *node = poly->head; node->next; node = node->next)
	{
		node->next->c *= num;
	}
	return poly;
}

// 多项式的幂
Poly *PowNum(Poly *poly, double e)
{
	Poly *temp;
	if (poly->head->next && !poly->head->next->next)
	{
		poly->head->next->e *= e;
		poly->head->next->c = pow(poly->head->next->c, e);
	}
	else if (e >= 2)
	{
		temp = ClonePoly(poly);
		for (int i = 0; i < e - 1; i++)
		{
			MulPoly(poly, temp);
		}
		ClearPoly(temp);
		free(temp);
	}
	else if (e == 1)
	{
	}
	else
	{
		return NULL;
	}
	return poly;
}

// 多项式求导
Poly *DiffPoly(Poly *poly)
{
	Node *p = poly->head;
	while (p->next)
	{
		p->next->c *= p->next->e;
		p->next->e--;
		if (p->next->c == 0)
		{
			Node *temp = p->next;
			p->next = temp->next;
			free(temp);
		}
		else
		{
			p = p->next;
		}
	}
	return poly;
}

// 多项式在特定 x 上的值
Poly *EvalPoly(Poly *poly, double num)
{
	double res = 0;
	for (Node *p = poly->head; p->next; p = p->next)
	{
		res += p->next->c * pow(num, p->next->e);
	}
	ClearPoly(poly);
	poly->head = NewNode(0, 0);
	poly->head->next = NewNode(res, 0);
	return poly;
}

#endif
